package com.fanpan26.algo.sort;

import java.util.Arrays;

/**
 * @author fanpan26
 */
public class MergeSort {

    //归并排序
    //将分成两段，然后加起来
    public static void main(String[] args) {
        int[] arr = {49, 38, 65, 97, 23, 22, 76, 1, 5, 8,};

        mergeSort(arr,arr.length);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr,int n){
        mergeSortInternally(arr,0,n-1);

    }

    private static void mergeSortInternally(int[] a,int p,int r){
        if (p>=r) {
            return;
        }
        //取中间值
        int q = p + (r-p) / 2;

        mergeSortInternally(a,p,q);
        mergeSortInternally(a,q+1,r);

        merge(a,p,q,r);
    }

    // [p...q] [q...r]
    private static void merge(int[] a,int p,int q,int r ){

        System.out.println(Arrays.toString(a));

         int i = p;
         int j =q+1;

         int k = 0;
         int[] temp = new int[r-p+1];
         while (i<=q&&j<=r){
             if (a[i]<a[j]){
                 temp[k++]=a[i++];
             }else{
                 temp[k++]=a[j++];
             }
         }
         //判断哪个有剩余
        int start = i;
        int end = q;

        if (j<=r){
            start = j;
            end = r;
        }
        while (start <= end) {
            temp[k++] = a[start++];
        }
        for (i = 0; i <= r-p; ++i) {
            a[p+i] = temp[i];
        }
    }

}
